﻿#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;


/*
实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列（即，组合出下一个更大的整数）。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
必须 原地 修改，只允许使用额外常数空间。


示例 1：
输入：nums = [1,2,3]
输出：[1,3,2]

示例 2：
输入：nums = [3,2,1]
输出：[1,2,3]

示例 3：
输入：nums = [1,1,5]
输出：[1,5,1]

示例 4：
输入：nums = [1]
输出：[1]
 

提示：
1 <= nums.length <= 100
0 <= nums[i] <= 100
*/



//class Solution1 {
//public:
//	void nextPermutation(vector<int>& nums) {
//		//	while (next_permutation(arr, arr+ totallen));
//		next_permutation(nums.begin(), nums.end());
//
//	}
//};

class Solution {
public:
	void nextPermutation(vector<int>& nums) {
		int i = 0;
		if (nums.size() <= 1) return;
		for (i = nums.size() - 2; i >= 0; i--) {
			if (nums[i] < nums[i + 1]) break;
		}
		if (i < 0) {
			reverse(nums.begin(), nums.end());
			return;
		}

		int j = 0;
		for (j = nums.size() - 1; j >i; j--) {
			if (nums[j] > nums[i]) {
				swap(nums[i],nums[j]);
				reverse(nums.begin()+i+1,nums.end());
				break;
			}
		}

		return;
	}
};

//
//int main() {
//
//	Solution s;
//	vector<int> v{2,2,0,4,3,1};
//	s.nextPermutation(v);
//
//	return 0;
//}
